#ifndef	_MH_STL_ALGORITHM_HPP_
#define	_MH_STL_ALGORITHM_HPP_

#include <mh/utility.hpp>

/*
 *	알고리즘
 */
namespace Mh
{
#ifndef min
	/*
	 *	min
	 *
	 *	\brief	두 인수 중 작은 것을 반환
	 *	\note	일부 헤더(windef.h 등)에서 매크로 함수로 선언되어 있을 경우에는 사용하지 않음
	 */
	template<typename T>
	const T& min( const T& a, const T& b )
	{
		return !(b < a) ? a : b;
	}

	template<typename T, typename Compare>
	const T& min( const T& a, const T& b, Compare comp )
	{
		return ( !comp( b, a ) ? a : b);
	}
#endif // min

#ifndef max
	/*
	 *	max
	 *
	 *	\brief	두 인수 중 큰 것을 반환
	 */
	template<typename T>
	const T& max( const T& a, const T& b )
	{
		return (a < b) ? b : a;
	}

	template<typename T, typename Compare>
	const T& max( const T& a, const T& b, Compare comp )
	{
		return ( comp( a, b ) ? b : a);
	}
#endif	// max

	/*
	 *	min_element
	 *
	 *	\brief	지정된 범위에서 가장 작은 것의 반복자를 반환
	 */
	template<typename ForwardIterator>
	ForwardIterator min_element( ForwardIterator first, ForwardIterator last )
	{
		ForwardIterator lowest = first;
		if( first == last ) return last;
		while( ++first != last )
			if( *first < *lowest )
				lowest = first;
		return lowest;
	}

	template<typename ForwardIterator, typename Compare>
	ForwardIterator min_element( ForwardIterator first, ForwardIterator last, Compare comp )
	{
		ForwardIterator lowest = first;
		if( first == last ) return last;
		while( ++first != last )
			if( comp(*first, *lowest) )
				lowest = first;
		return lowest;
	}

	/*
	 *	max_element
	 *
	 *	\brief	지정된 범위에서 가장 큰 것의 반복자를 반환
	 */
	template<typename ForwardIterator>
	ForwardIterator max_element( ForwardIterator first, ForwardIterator last )
	{
		ForwardIterator largest = first;
		if( first == last ) return last;
		while( ++first != last )
			if( *largest < *first )
				largest = first;
		return largest;
	}

	template<typename ForwardIterator, typename Compare>
	ForwardIterator max_element( ForwardIterator first, ForwardIterator last, Compare comp )
	{
		ForwardIterator largest = first;
		if( first == last ) return last;
		while( ++first != last )
			if( comp( *largest, *first ) )
				largest = first;
		return largest;
	}

	/*!
	 *	minmax()
	 *
	 *	\breif	두 요소의 크기를 비교한후 pair로 반환
	 *	\note	C++11에서 추가됨
	 *	\todo	initializer_list를 사용한 것이 2개 더 있는데 나중에...
	 */
	template<typename T>
	pair<const T&, const T&> minmax( const T& a, const T& b )
	{
		return ( b < a ? make_pair( b, a ) : make_pair( a, b ) );
	}

	template<typename T, typename Compare>
	pair<const T&, const T&> minmax( const T& a, const T& b, Compare comp )
	{
		return ( comp( b, a ) ? make_pair( b, a ) : make_pair( a, b ) );
	}

	/*!
	 *	swap()
	 *
	 *	\brief	두 객체의 값을 바꿈
	 *	\note	C++11에서 람다를 이용하는 추가함수가 있지만 나중에.
	 */
	template<typename T>
	void swap( T& a, T& b )
	{
		T temp( b );
		b = a;
		a = temp;
	}

	// 이하 특수화. 특수화된 게 좀 많음. 이건 각 헤더에 넣아야함;
//	template<typename T, size_t N>
//	void swap( array<T,N>& lhs, array<T,N>& rhs );

	/*!
	 *	iter_swap()
	 *
	 *	\brief	반복자가 가리키는 값을 바꿈
	 */
	template<typename ForwardIterator1, typename ForwardIterator2>
	void iter_swap( ForwardIterator1 a, ForwardIterator2 b )
	{
		swap(*a, *b);
	}

	/*!
	 *	swap_ranges()
	 *
	 *	\brief	범위 지정 스왑
	 */
	template<typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 swap_ranges( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
	{
		while( first1 != last1 )
			iter_swap( first1++, first2++ );
		return first1;
	}

	/*!
	 *	reverse()
	 *
	 *	\brief	범위의 값을 역순으로 함
	 */
	template<typename BidirectionalIterator>
	void reverse( BidirectionalIterator first, BidirectionalIterator last )
	{
		while( (first != last) && (first != --last) )
			swap(*first++, *last);
	}

	/*!
	 *	reverse_copy()
	 *
	 *	\brief	범위의 값을 뒤집어서 지정한 곳에 복사
	 */
	template<typename BidirectionalIterator, typename OutputIterator>
	OutputIterator reverse_copy( BidirectionalIterator first, BidirectionalIterator last, OutputIterator dest )
	{
		while( (first != last) && (first != --last) )
			*dest++ = *last;
	}

	/*!
	 *	rotate()
	 *
	 *	\brief	특정 범위를 두 부분으로 나눠서 값을 바꿈
	 *	\note	C++11에서 반환값이 void에서 마지막 값으로 바뀜
	 */
	template<typename ForwardIterator>
	ForwardIterator rotate( ForwardIterator first, ForwardIterator n_first, ForwardIterator last )
	{
		ForwardIterator next = n_first;
		while( first != last )
		{
			swap( *first, *next );
			++first, ++next;
			if( next == last )
				next = n_first;
			else if( first == n_first )
				n_first = next;
		}
		return first;
	}

	/*!
	 *	rotate_copy()
	 */
	template<typename ForwardIterator, typename OutputIterator>
	OutputIterator rotate_copy( ForwardIterator first, ForwardIterator n_first, ForwardIterator last, OutputIterator dest )
	{
		dest = copy( n_first, last, dest );
		return copy( first, n_first, dest );
	}

	/*!
	 *	unique()	 
	 */
	template<typename ForwardIterator>
	ForwardIterator unique( ForwardIterator first, ForwardIterator last )
	{
		ForwardIterator result = first;
		while( ++first != last )
		{
			if( !(*result == *first) )
				*(++result) = *first;
		}
		return ++result;
	}

	template<typename ForwardIterator, typename BinaryPredicate>
	ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate pred )
	{
		ForwardIterator result = first;
		while( ++first != last )
		{
			if( !pred(*result, *first) )
				*(++result) = *first;
		}
		return ++result;
	}

	/*!
	 *	unique_copy()
	 */
	template<typename ForwardIterator, typename OutputIterator>
	OutputIterator unique_copy( ForwardIterator first, ForwardIterator last, OutputIterator dest )
	{
		*dest = *first;
		while( ++first != last )
		{
			if( !(*dest == *first) )
				*(++dest) = *first;
		}
		return ++dest;
	}

	template<typename ForwardIterator, typename OutputIterator, typename BinaryPredicate>
	OutputIterator unique_copy( ForwardIterator first, ForwardIterator last, OutputIterator dest, BinaryPredicate pred )
	{
		*dest = *first;
		while( ++first != last )
		{
			if( !pred(*dest, *first) )
				*(++dest) = *first;
		}
		return ++dest;
	}
	
	/*!
	 *	for_each()
	 */
	template<typename InputIterator, typename Function>
	Function for_each( InputIterator first, InputIterator last, Function f )
	{
		for( ; first != last; ++first ) f(*first);
		return f;
	}


	/*!
	 *	find()
	 *
	 *	\brief	범위 내에서 특정 값을 가진 첫번째 요소를 검색
	 */
	template<typename InputIterator, typename T>
	InputIterator find( InputIterator first, InputIterator last, const T& value )
	{
		for( ; first != last; ++first ) if( *first == value ) break;
		return first;
	}

	/*!
	 *	find_if()
	 *
	 *	\brief	범위 내에서 지정한 조건을 만족하는 첫번째 요소를 검색
	 */
	template<typename InputIterator, typename Predicate>
	InputIterator find_if( InputIterator first, InputIterator last, Predicate pred )
	{
		for( ; first != last; ++first )
			if( pred(*first) ) break;
		return first;
	}

	/*!
	 *	find_if_not()
	 *
	 *	\brief	범위 내에서 지정한 조건을 만족하지 않는 첫번재 요소를 검색
	 *	\note	C++11에서 추가됨
	 */
	template<typename InputIterator, typename UnaryPredicate>
	InputIterator find_if_not( InputIterator first, InputIterator last, UnaryPredicate )
	{
		for( ; first != last; ++first )
			if( !pred(*first) ) break;
		return first;
	}

	/*!
	 *	find_end()
	 *
	 *	\brief	범위 내에서 조건을 만족하는 마지막 요소를 검색
	 */
	template<typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 find_end( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 )
	{
		if (first2==last2)
			return last1;  // specified in C++11
		
		ForwardIterator1 ret = last1;		
		while (first1!=last1)
		{
			ForwardIterator1 it1 = first1;
			ForwardIterator2 it2 = first2;
			while (*it1 == *it2)
			{
				++it1; ++it2;
				if (it2 == last2) { ret=first1; break; }
				if (it1 == last1) return ret;
			}
			++first1;
		}
		return ret;
	}

	template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1 find_end( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred )
	{
		if (first2==last2)
			return last1;  // specified in C++11
		
		ForwardIterator1 ret = last1;
		
		while (first1!=last1)
		{
			ForwardIterator1 it1 = first1;
			ForwardIterator2 it2 = first2;
			while ( pred(*it1, *it2) )
			{
				++it1; ++it2;
				if (it2==last2) { ret=first1; break; }
				if (it1==last1) return ret;
			}
			++first1;
		}
		return ret;
	}

	/*!
	 *	find_first_of()
	 */
	template<typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 )
	{
		for ( ; first1 != last1; ++first1 )
			for (ForwardIterator2 it=first2; it!=last2; ++it)
				if ( *it == *first1 )
					return first1;
		return last1;
	}

	template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1 find_first_of( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred )
	{
		for ( ; first1 != last1; ++first1 )
			for (ForwardIterator2 it=first2; it!=last2; ++it)
				if ( pred( *it, *first1) )
					return first1;
		return last1;
	}

	/*
	 *	adjacent_find
	 */
	template<typename ForwardIterator>
	ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last )
	{
		if( first != last )
		{
			ForwardIterator next = first;
			++next;
			while( next != last )
				if( *first++ == *next++ )
					return next
		}
		return last;
	}

	template<typename ForwardIterator, typename BinaryPredicate>
	ForwardIterator adjacent_find( ForwardIterator first, ForwardIterator last, BinaryPredicate pred )
	{
		if( first != last )
		{
			ForwardIterator next = first;
			++next;
			while( next != last )
				if( pred(*first++, *next++) )
					return next
		}
		return last;
	}

	template<typename ForwardIterator, typename T>
	ForwardIterator remove( ForwardIterator first, ForwardIterator last, const T& value )
	{
		ForwardIterator result = first;
		for( ; first != last; ++first )
			if( !(*first == value) ) *result++ = *first;
		return result;
	}

	/*
	 *	search()
	 */
	template<typename ForwardIterator1, typename ForwardIterator2>
	ForwardIterator1 search( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 s_first, ForwardIterator2 s_last )
	{
		ForwardIterator1 t_last = first;
		size_t cmp_len = distance( first, last ) - distance( s_first, s_last ) + 1;
		advance( t_last, cmp_len );

		for( ; first != t_last; ++first )
		{
			ForwardIterator1 iter = first;
			ForwardIterator2 s_iter = s_first;
			while( *iter == *s_iter )
			{
				++iter;
				++s_iter;

				if( iter == s_iter )
					return first;
			}
		}
		return last;
	}

	template<typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
	ForwardIterator1 search( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 s_first, ForwardIterator2 s_last, BinaryPredicate pred )
	{
		ForwardIterator1 t_last = first;
		size_t cmp_len = distance( first, last ) - distance( s_first, s_last ) + 1;
		advance( t_last, cmp_len );

		for( ; first != t_last; ++first )
		{
			ForwardIterator1 iter = first;
			ForwardIterator2 s_iter = s_first;
			while( pred(*iter, *s_iter) )
			{
				++iter;
				++s_iter;

				if( iter == s_iter )
					return first;
			}
		}
		return last;
	}

	/*!
	 *	copy()
	 *
	 *	\brief	범위 복사
	 */
	template<typename InputIterator, typename OutputIterator>
	OutputIterator copy( InputIterator first, InputIterator last, OutputIterator dest )
	{
		while( first != last )
		{
			*dest = *first;
			++first, ++dest;
		}
		return dest;
	}

	/*!
	 *	copy_if()
	 *
	 *	\brief	범위 내의 조건을 만족하는 요소를 다른 곳에 복사함
	 *	\note	C++11에서 추가됨
	 */
	template<typename InputIterator, typename OutputIterator, typename UnaryPredicate>
	OutputIterator copy_if( InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred )
	{
		while( first != last )
		{
			if( pred(first) )
			{
				*last = *first;
				++last;
			}
			++first;
		}
		return result;
	}

	/*!
	 *	copy_n()
	 *
	 *	\brief	지정한 위치에서 n개의 요소를 복사
	 *	\note	C++11에서 추가됨
	 */
	template<typename InputIterator, typename Size, class OutputIterator>
	OutputIterator copy_n( InputIterator first, Size count, OutputIterator result )
	{
		// count <= 0 일때는 아무것도 하지 않음
		if( count > 0 )
		{
			*result++ = *first;
			for( Size i = 1; i < count; ++i )
			{
				*result = *(++first);
				++result;
			}
		}
		return result;
	}
	
	/*!
	 *	copy_backward()
	 *
	 *	\brief	역방향으로 범위 복사
	 */
	template<typename BidirectionalIterator1, typename BidirectionalIterator2>
	BidirectionalIterator2 copy_backward( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result )
	{
		while( last != first )
			*(--result) = *(--last);
		return result;
	}

	/*!
	 *	fill()
	 *
	 *	\brief	범위 내를 값으로 채움
	 */
	template<typename ForwardIterator, typename T>
	void fill( ForwardIterator first, ForwardIterator last, const T& value )
	{
		for(; first != last; ++first )
			*first = value;
	}

	/*!
	 *	fill_n()
	 *
	 *	\brief	
	 */
	template<typename OutputIterator, class Size, class T>
	OutputIterator fill_n( OutputIterator first, Size count, const T& value )
	{
		for( Size i = 0; i < count; ++i )
			*first++ = value;
		return first;
	}

	/*!
	 *	count()
	 *
	 *	\brief	범위 내에 특정 값을 가진 개체의 수를 조사
	 */
	template<typename InputIterator, typename T>
	ptrdiff_t count( InputIterator first, InputIterator last, const T& value )
	{
		ptrdiff_t ret = 0;
		while( first != last )
		{
			if( *first == value )
				++ret;

			++first;
		}
		return ret;			
	}

	/*!
	 *	count_if()
	 */
	template <typename InputIterator, typename Predicate>
	ptrdiff_t count_if( InputIterator first, InputIterator last, Predicate pred )
	{
		ptrdiff_t ret=0;
		while (first != last)
		{
			if( pred( *first ) )
				++ret;

			++first;
		}
		return ret;
	}

	/*!
	 *	mismatch()
	 *
	 */
	template<typename InputIterator1, typename InputIterator2>
	pair<InputIterator1, InputIterator2> mismatch( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
	{
		for( ; first1 != last1; ++first1, ++first2 )
		{
			if( *first1 != *first2 )
				break;
		}
		return make_pair( first1, first2 );
	}

	template<typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
	pair<InputIterator1, InputIterator2> mismatch( InputIterator1 first, InputIterator1 last, InputIterator2 first2, BinaryPredicate pred )
	{
		for( ; first1 != last1; ++first1, ++first2 )
		{
			if( !pred(*first1, *first2) )
				break;
		}
		return make_pair( first1, first2 );
	}
	
	/*!
	 *	equal()
	 */
	template <typename InputIterator1, typename InputIterator2>
	bool equal( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
	{
		while( first1!=last1 )
		{
			if( !(*first1 == *first2) )
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
	bool equal( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred )
	{
		while ( first1!=last1 )
		{
			if( !pred(*first1, *first2) )
				return false;

			++first1;
			++first2;
		}
		return true;
	}

	template <typename ForwardIterator, typename T>
	pair<ForwardIterator,ForwardIterator> equal_range( ForwardIterator first, ForwardIterator last, const T& value )
	{
		ForwardIterator it = lower_bound (first,last,value);
		return make_pair ( it, upper_bound(it,last,value) );
	}

	/*!
	 *	partition()
	 *
	 *	\brief	범위내의 요소들을 분할
	 *	\note	C++11에서는 양방향이 아니라 전방향반복자로 바뀜... 일단 지금은 무시하자
	 */
	template<typename BidirectionalIterator, class UnaryPredicate>
	BidirectionalIterator partition( BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred )
	{
		while( true )
		{
			while( (first != last) && pred(*first) )
				++first;			// 조건을 만족하지 않는 요소를 검색
			if( first == last-- )
				break;				// 그게 마지막 요소면 분할 끝
			
			while( (first != last) && !p(*last) )
				--last;				// 조건을 만족하는 요소를 뒷쪽에서부터 검색
			if( first == last )
				break;				// 위에서 찾은 요소까지 달리 없으면 분할 끝
			
			swap( *first, *last );	// 두 요소를 스왑
			++first;
		}
		return first;
	}

	/*!
	 *	is_partitioned()
	 *
	 *	\brief	범위 내의 요소들이 주어진 조건에 따라 분할되어 있는지 검증
	 *	\note	C++11에서 추가됨
	 */
	template<typename InputIterator, typename UnaryPredicate>
	bool is_partitioned( InputIterator first, InputIterator last, UnaryPredicate pred )
	{
		for( ; first != last; ++first )
			if( !p(first) )		// 조건을 만족하지 않는곳(분할경계)까지 이동
				break;

		for( ; first != last; ++first )
			if( p(first) )		// 경계를 넘어섰는데 조건을 만족하면 제대로 분할되지 않은 것
				return false;

		return true;
	}

	/*!
	 *	partition_copy()
	 *
	 *	\brief	특정 범위의 요소를 주어진 조건에 따라 분할하여 지정한 곳에 각각 복사함
	 *	\note	C++11에서 추가됨
	 */
	template<typename InputIterator, typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate>
	pair<OutputIterator1, OutputIterator2> partition_copy( InputIterator first, InputIterator last, OutputIterator1 result_true, OutputIterator2 result_false, UnaryPredicate pred )
	{
		while( first != last )
		{
			if( p(*first) )
			{
				*result_true = *first;
				++result_true;
			}
			else
			{
				*result_false = *first;
				++result_false;
			}
			++first;
		}
		return pair<OutputIterator1, OutputIterator2>( result_true, result_false );
	}

}	// namespace Mh

#endif	/* _MH_STL_ALGORITHM_HPP_ */